package binaryTree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author king
 */
public class PreorderTraversal {

	/** 递归前序遍历 */
	public LinkedList<Integer> rePreorderTrav(TreeNode root){
		LinkedList<Integer> nodes = new LinkedList<>();
		dfs(root, nodes);
		return nodes;
	}

	private void dfs(TreeNode root, LinkedList<Integer> nodes){
		if(root != null){
			nodes.offer(root.val);
			dfs(root.left, nodes);
			dfs(root.right, nodes);
		}
	}

	/** 迭代前序遍历 */
	public LinkedList<Integer> loopPreorderTrav(TreeNode root){
		LinkedList<Integer> nodes = new LinkedList<>();
		Deque<TreeNode>	 stack = new ArrayDeque<>();
		TreeNode curNode = root;
		while(curNode != null || !stack.isEmpty()){
			while(curNode != null){
				//根
				nodes.offer(curNode.val);
				//结点入栈，用于后面遍历右子树
				stack.offerLast(curNode);
				//左子树
				curNode = curNode.left;
			}
			curNode = stack.pollLast();
			//右子树
			curNode = curNode.right;
		}
		return nodes;
	}
}
